{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homogeneous coordinates. Geometry"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cross product of two lines gives an intersection point\n",
    "If two lines are defined in homogeneous coordinates, we can find the intersection point as cross product of two lines.\n",
    "\n",
    "**Check**\n",
    "\n",
    "Let's assume we have $l_1= [a,b,c]^T$ and $l_2 = [d,e,f]^T$, then traditionally to find the point that belong to the line, we need to solve the system of linear equations.\n",
    "$$\n",
    "    \\begin{cases} \n",
    "    ax + by + c = 0 \\\\\n",
    "    dx + ey + f = 0 \\\\\n",
    "    \\end{cases}\n",
    "$$\n",
    "taken $x$ from first equation results in $x = \\frac{-c-by}{a}$ then substituting x into second equation, we will have\n",
    "$$\n",
    "   \\begin{array} {lcl} \n",
    "       \\frac{d}{a}(-c-by)+ey+f = 0\\\\\n",
    "       -\\frac{d}{a} - \\frac{db}{a}y + ey +f = 0 \\\\\n",
    "       (e-\\frac{db}{a}y = \\frac{dc}{a}- f) \\\\\n",
    "       y = \\frac{dc-fa}{ea-db}\n",
    "    \\end{array} \n",
    "$$\n",
    "\n",
    "Substituting $y$ back to find $x$, we need to perform a sequence of simplifications:\n",
    "$$\n",
    "   \\begin{array} {lcl} \n",
    "        x &=& -\\frac{c}{a}- \\frac{b}{a}(\\frac{dc-fa}{ea-db}) \\\\\n",
    "          &=& \\frac{1}{a}\\left(\\frac{-c(ae-bd)-b(cd-af)}{ae-bd}\\right) \\\\ \n",
    "          &=& \\frac{1}{a(ae-bd)}\\left(-cae+cbd-bcd+baf\\right) \\\\\n",
    "          &=&  \\frac{-cae+baf)}{a(ae-bd)} = \\frac{a(bf-ec)}{a(ae-bd)} = \\frac{bf-ec}{ae-bd}\n",
    "    \\end{array} \n",
    "$$\n",
    "\n",
    "So solving the system of linear equations, we have:\n",
    "$$\n",
    "    \\begin{cases} \n",
    "    x= \\frac{bf-ec}{ae-bd} \\\\\n",
    "    y = \\frac{dc-fa}{ea-db}\n",
    "    \\end{cases}\n",
    "$$\n",
    "\n",
    "Showing that by decomposing the cross product we will get the same results\n",
    "$$\n",
    "\\begin{array} {lcl}\n",
    "    l_1 \\times l_2 &=&\n",
    "    \\begin{bmatrix} \n",
    "       i & j & k \\\\\n",
    "       a & b & c \\\\\n",
    "       d & e & f \n",
    "     \\end{bmatrix} =  i \\begin{bmatrix}b & c \\\\ e &f \\end{bmatrix} -\n",
    "    j \\begin{bmatrix}a & c \\\\ d & f \\end{bmatrix} + k \\begin{bmatrix}a & b \\\\ d & e \\end{bmatrix} \\\\\n",
    "    &=& (bf-ec)i - j(af-cd) + k(ae-bd) \\\\\n",
    "    &=& (bf-ec)i + (cd-af)j + k(ae-bd)\n",
    "\\end{array} \n",
    "$$\n",
    "Rewriting it a little bit leads to\n",
    "$$\n",
    "    \\begin{bmatrix}i\\\\ j\\\\ k \\end{bmatrix} = \n",
    "        \\begin{bmatrix} bf-ec \\\\ cd-af \\\\ ae-bd \\end{bmatrix} = \n",
    "        \\begin{bmatrix} \\frac{bf-ec}{ae-bd} \\\\ \\frac{cd-af}{ae-bd} \\\\ 1 \\end{bmatrix} = \n",
    "        \\begin{bmatrix} x \\\\ y \\\\ 1 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "**Checked**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution sys:  [3. 3.]\n",
      "Solution cross:  [3. 3. 1.]\n"
     ]
    }
   ],
   "source": [
    "## Checking this with l1:= y=3 and l2 := y=x\n",
    "import numpy as np\n",
    "\n",
    "## data\n",
    "A = np.matrix([[0,1], [-1,1]])\n",
    "b = np.array([3,0])\n",
    "l1 = np.array([0,1,-3])\n",
    "l2 = np.array([-1,1,0])\n",
    "\n",
    "## solving\n",
    "sol_sys =  np.linalg.solve(A,b)\n",
    "print(\"Solution sys: \", sol_sys)\n",
    "sol_cross = np.cross(l1,l2)\n",
    "sol_cross = sol_cross /sol_cross[2]\n",
    "print(\"Solution cross: \", sol_cross)\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "fig=plt.figure(1)\n",
    "x = np.arange(-2, 6, 0.1)\n",
    "n = x.shape[0]\n",
    "y1 = [3]*n  ## generates vector of n elements all has value 3\n",
    "y2 = x \n",
    "plt.plot(x, y1, 'r')\n",
    "plt.plot(x, y2, 'b');\n",
    "plt.grid(linestyle='--', linewidth=1);\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution cross:  [4 0 0]\n"
     ]
    }
   ],
   "source": [
    "## Checking with parallel lines y = 3 and y = -1\n",
    "\n",
    "## data\n",
    "A = np.matrix([[-1,1], [-1,1]])\n",
    "b = np.array([3,-1])\n",
    "l1 = np.array([0,1,-3])\n",
    "l2 = np.array([0,1,1])\n",
    "\n",
    "## solving\n",
    "# sol_sys =  np.linalg.solve(A,b) ---> crashes as expected\n",
    "# print(\"Solution sys: \", sol_sys)\n",
    "sol_cross = np.cross(l1,l2)  ## --> solution exists, but point to the infinity\n",
    "# sol_cross = sol_cross /sol_cross[2]  --> impossible, division by zero\n",
    "print(\"Solution cross: \", sol_cross)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  Cross product of homogenous points gives a line that passes through them\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-4 -7 19]\n"
     ]
    }
   ],
   "source": [
    "p1 = np.array([3, 1, 1])\n",
    "p2 = np.array([-4, 5, 1])\n",
    "\n",
    "l = np.cross(p1,p2)\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
